package Hot100;

import java.util.Stack;

/**
 * @author zhangmin
 * @create 2022-01-15 15:30
 */
public class dailyTemperatures739 {
    /**
     * 739. 每日温度
     * 请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
     * 单调栈。寻找下一个更好的元素。从后向前在栈中加入元素，若栈顶元素比当前元素小则pop出，保存栈内单调增。当元素入栈时，计算其余前一个栈顶元素的距离即为答案
     * */
    public int[] dailyTemperatures(int[] temperatures) {
        int n=temperatures.length;
        Stack<Integer> stack=new Stack<>();
        int[] res=new int[n];
        for (int i = n-1; i >=0 ; i--) {
            while (!stack.isEmpty()&&temperatures[stack.peek()]<=temperatures[i]){
                stack.pop();
            }
            if (stack.isEmpty()){
                res[i]=0;
            }else {
                res[i]=stack.peek()-i;
            }
            stack.push(i);
        }
        return res;
    }
}
